#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>

const int mod = 998244353;
const int N = 5e5 + 10;
ll fac[N], ifac[N], inv[N];
void init() {
    fac[0] = ifac[0] = ifac[1] = inv[1] = 1;
    for(int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
        if(i > 1) ifac[i] = (mod - mod / i) * ifac[mod % i] % mod, inv[i] = ifac[i];
    }
    for(int i = 1; i < N; i++) ifac[i] = ifac[i - 1] * ifac[i] % mod;
}
ll C(int n, int m) {
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
ll ksm(ll a, ll b = mod - 2) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b /= 2;
    }
    return res;
} 


int phi[N], visi[N], pri[N], cnt;
void init_phi() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!visi[i]) {
            visi[i] = i;
            pri[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt; j++) {
            int id = pri[j] * i;
            if(id >= N) break;
            visi[id] = pri[j];
            if(i % pri[j] == 0) {
                phi[id] = phi[i] * pri[j];
                break;
            }
            phi[id] = phi[i] * phi[pri[j]];
        }
    }
}

/*
杜教筛模板
s = sumf, f * g = h; gs hs需要O(1)算
phi * I = id, mu * I = e
*/
struct Djs {
    vector<ll>& s;
    map<ll, ll> mp;

    Djs(vector<ll> &s_) : s(s_){}

    template<class F1, class F2>
    ll wk(ll n, F1&& gs, F2&& hs) {
        if (n < s.size()) return s[n];
        auto it = mp.find(n);
        if (it != mp.end()) return it->second;

        ll res = hs(n);
        for (ll l = 2, r = 0; l <= n; l = r + 1) {
            r = n / (n / l);
            res -= wk(n / l, gs, hs) * (gs(r) - gs(l - 1));
        }    
        res /= gs(1);
        return mp[n] = res;
    }
};
// 预处理所求函数的前缀和数组
const int N = 5e6;
vector<ll> phi, visi, pri, mu; int cnt = 0;
void init() {
    phi.resize(N); visi = pri = mu = phi;

    phi[1] = 1; mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!visi[i]) {
            visi[i] = i;
            pri[++cnt] = i;
            phi[i] = i - 1;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt; j++) {
            int id = pri[j] * i;
            if(id >= N) break;
            visi[id] = pri[j];
            mu[id] = (i % pri[j] ? -mu[i] : 0);
            if(i % pri[j] == 0) {
                phi[id] = phi[i] * pri[j];
                break;
            }
            phi[id] = phi[i] * phi[pri[j]];
        }
    }
    for (int i = 2; i < N; i++) phi[i] += phi[i - 1], mu[i] += mu[i - 1];
}


const int mod = 1e9 + 7;
struct Matrix {
    int n;
    vector<vector<ll>> a;
    Matrix(int n_) : n(n_) {
        a.assign(n, vector<ll> (n));
    }
    void asign(int i, int j, ll val) {
        a[i][j] = val;
    }
    Matrix operator*(const Matrix & t) const& {
        Matrix res(n);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    res.a[i][j] += a[i][k] * t.a[k][j];
                    if(mod) res.a[i][j] %= mod;
                }
            }
        }
        return res;
    }
    Matrix ksm(Matrix &A, ll n) {
        if(n == 0) {
            Matrix res(A.n);
            for(int i = 0; i < A.n; i++) res.a[i][i] = 1;
            return res;
        }
        if(n & 1) return ksm(A, n - 1) * A;
        auto res = ksm(A, n / 2);
        return res * res;
    }
    Matrix ksm(ll n) {
        return ksm(*this, n);
    }
};




const int mod = 998244353;
const int N = 4e5 + 10;
ll fac[N], ifac[N], inv[N];
void init() {
    fac[0] = ifac[0] = ifac[1] = inv[1] = 1;
    for(int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
        if(i > 1) ifac[i] = (mod - mod / i) * ifac[mod % i] % mod, inv[i] = ifac[i];
    }
    for(int i = 1; i < N; i++) ifac[i] = ifac[i - 1] * ifac[i] % mod;
}
ll C(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
template<int P = mod>
ll ksm(ll a, ll b = P - 2) {
    a %= P;
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % P;
        a = a * a % P, b /= 2;
    }
    return res;
} 

int g, gi;
vector<int> R; 
int init_ntt(int n) {
    int len = 1;
    while (len <= n) len *= 2;
    g = 3, gi = ksm(3);
    
    R.resize(len);
    for(int i = 0; i < len; i++) R[i] = R[i / 2] / 2 + ((i & 1) ? len / 2 : 0);
    return len;
}

// 每次使用ntt必须处理这玩意
template<int P = mod>
void ntt(vector<int> &A, int opt) {
    int n = A.size();
    gi = ksm<P>(g);
    for(int i = 0; i < n; i++) if(R[i] > i) swap(A[i], A[R[i]]);
    for(int m = 2; m <= n; m *= 2) {
        int w1 = ksm<P>((opt == 1 ? g : gi), (P - 1) / m);
        for(int i = 0; i < n; i += m) {
            int w = 1;
            for(int j = 0; j < m / 2; j++) {
                int x = A[i + j], y = 1ll * A[i + j + m / 2] * w % P;
                int v1 = x + y; if(v1 >= P) v1 -= P;
                int v2 = x - y; if(v2 < 0) v2 += P;
                A[i + j] = v1, A[i + j + m / 2] = v2, w = 1ll * w * w1 % P;
            }
        }
    }	
    if(opt == -1) for(int i = 0, in = ksm<P>(n); i < n; i++) A[i] = (A[i] * 1ll * in) % P;
}
// 末尾一定无0，所以某些情况特判越界。
vector<int> operator* (vector<int> a, vector<int> b) {
    int n = (int)a.size() - 1, m = (int)b.size() - 1;
    for(m = n + m, n = 1; n <= m; n *= 2);
    a.resize(n), b.resize(n);
    g = 3, gi = ksm(3);
    
    R.resize(n);
    for(int i = 0; i < n; i++) R[i] = R[i / 2] / 2 + ((i & 1) ? n / 2 : 0);
    ntt(a, 1), ntt(b, 1);
    for(int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % mod;
    ntt(a, -1);
    while(a.size() && a.back() == 0) a.pop_back();
    return a;
}
vector<int> operator+ (vector<int> a, vector<int> b) {
    int n = max(a.size(), b.size());
    a.resize(n), b.resize(n);
    for (int i = 0; i < n; i++) {
        int x = a[i] + b[i];
        if (x > mod) x -= mod;
        a[i] = x;
    }
    return a;
}
vector<int> operator- (vector<int> a, vector<int> b) {
    int n = max(a.size(), b.size());
    a.resize(n), b.resize(n);
    for (int i = 0; i < n; i++) {
        int x = a[i] - b[i];
        if (x < 0) x += mod;
        a[i] = x;
    }
    return a;
}
// a[0] != 0
vector<int> Inv(vector<int> a, int n) {
    a.resize(n);
    if (n == 1) {
        return {(int)ksm(a[0])};
    }
    int len = (n + 1) / 2;
    auto f0 = Inv(a, len);

    int tot = init_ntt(n * 2);
    f0.resize(tot), a.resize(tot);
    ntt(f0, 1), ntt(a, 1);
    for (int i = 0; i < tot; i++) {
        f0[i] = (2 - a[i] * 1ll * f0[i] % mod + mod) * f0[i] % mod;
    }
    ntt(f0, -1);
    f0.resize(n);
    return f0;
}

// 多项式求导
vector<int> Derivative(vector<int> g) {
    int n = g.size();
    vector<int> f(n);
    for (int i = 0; i < n - 1; i++) {
        f[i] = g[i + 1] * 1ll * (i + 1) % mod;
    }
    return f;
}
// 多项式积分，结果常数项为0
vector<int> Integral(vector<int> g) {
    int n = g.size();
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++) {
        f[i] = g[i - 1] * 1ll * inv[i] % mod;
    }
    return f;
}
// 多项式ln，要求g的常数项为1
vector<int> Ln(vector<int> g, int n) {
    g.resize(n);
    auto t = Derivative(g) * Inv(g, n);
    t.resize(n);
    auto res = Integral(t);
    return res;
}

// 多项式exp，要求h的常数项为0  
// 1e5 400ms
vector<int> Exp(vector<int> h, int n) {
    h.resize(n);
    if (n == 1) {
        return {1};
    }
    int len = n + 1 >> 1;
    auto f0 = Exp(h, len);

    auto lf = Ln(f0, n);
    int tot = init_ntt(n * 2);
    f0.resize(tot), h.resize(tot), lf.resize(tot);
    ntt(f0, 1), ntt(h, 1), ntt(lf, 1);
    for (int i = 0; i < tot; i++) {
        ll x = f0[i] * 1ll * (1 - lf[i] + h[i]) % mod;
        if (x < 0) x += mod;
        f0[i] = x;
    }
    ntt(f0, -1);
    f0.resize(n);
    return f0;
}
// 多项式开根，要求a0为0
vector<int> Sqrt(vector<int> a, int n) {
    a.resize(n);
    if (n == 1) {
        assert(a[0] == 1);
        return {1};
    }
    int len = n + 1 >> 1;
    auto f0 = Sqrt(a, len);

    f0 = f0 + a * Inv(f0, n);
    f0.resize(n);
    ll i2 = ksm(2);
    for (auto &x : f0) x = x * i2 % mod;
    return f0;
}
vector<int> rshift(vector<int> a, int k = 1) {
    while (k--)
        a.insert(a.begin(), 0);
    return a;
}
vector<int> Ksm1(vector<int> a, ll k, int n) {
    a = Ln(a, n);
    for (auto &x : a) x = x * k % mod;
    return Exp(a, n);
};
// a 的k次方， k不能先取模，如果k过大需要在*处修改
// 1e5 400ms
vector<int> Ksm(vector<int> a, ll k, int n) {
    a.resize(n);
    int id = n;
    for (int i = 0; i < n; i++) {
        if (a[i]) {
            id = i;
            break;
        }
    }
    // * 原始的k和id和大于n
    if ((lll)id * k >= n) {
        return vector<int>(n, 0);
    }
    vector<int> b(a.begin() + id, a.end());
    ll v = ksm(b[0]), vv = ksm(b[0], k); //* 这里如果k过大要用费马小定理模为mod - 1
    for (auto &x : b) x = x * v % mod;
    b = Ksm1(b, k, n - id * k);
    a = vector<int> (id * k, 0);
    for (auto x : b) a.push_back(x * vv % mod);
    return a;
};

// const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
constexpr int P[3] = {998244353, 1004535809, 469762049};

// 末尾一定无0，所以某些情况特判越界。
template<int P = mod>
vector<int> mttMul1 (vector<int> a, vector<int> b) {
    gi = ksm<P>(g); // 对于每个模数的gi都不一样，要注意
    int n = a.size();
    ntt<P>(a, 1), ntt<P>(b, 1);
    
    for(int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % P;
    ntt<P>(a, -1);
    while(a.size() && a.back() == 0) a.pop_back();
    a.resize(n);
    return a;
}
// 150ms 1e5
vector<int> mttMul(vector<int> a, vector<int> b, ll p) {
    int n = (int)a.size() - 1, m = (int)b.size() - 1;
    int tot = init_ntt(n + m);
    a.resize(tot), b.resize(tot);
    vector res(3, vector<int>());
    res[0] = mttMul1<P[0]>(a, b);
    res[1] = mttMul1<P[1]>(a, b);
    res[2] = mttMul1<P[2]>(a, b);

    vector<int> ans(tot);

    lll pp = P[0] * (lll) P[1] * P[2];
    vector<lll> M(3), ii(3);
    for (int i = 0; i < 3; i++) {
        M[i] = pp / P[i];
    }
    ii[0] = ksm<P[0]>(M[0]) * M[0] % pp;
    ii[1] = ksm<P[1]>(M[1]) * M[1] % pp;
    ii[2] = ksm<P[2]>(M[2]) * M[2] % pp;

    for (int i = 0; i < tot; i++) {
        lll tmp = 0;
        // db(i, res[0][i], res[1][i], res[2][i]);
        for (int t = 0; t < 3; t++) {
            tmp += res[t][i] * ii[t] % pp;
        }
        ans[i] = tmp % pp % p;
    }
    return ans;
}

// 500ms 1e5
template<int P = mod>
vector<int> mttInv(vector<int> a, int n) {
    a.resize(n);
    if (n == 1) {
        return {(int)ksm<P>(a[0])};
    }
    int len = (n + 1) / 2;
    auto f0 = mttInv<P>(a, len);

    a = mttMul(a, f0, P);
    a.resize(n);
    for (int i = 0; i < n; i++) {
        a[i] = (i == 0) * 2 - a[i];
        if (a[i] < 0) a[i] += P;
    }
    a = mttMul(a, f0, P);
    a.resize(n);
    return a;
}


// 拉格朗日差值，给定点对求一个点值，n方
ll lagrange(vector<int> x, vector<int> y, int k) {
    int n = x.size();
    assert(n == y.size());
    ll res = 0;
    for (int i = 0; i < n; i++) {
        ll resi = y[i];
        ll A = 1, B = 1;
        for (int j = 0; j < n; j++) if (i ^ j) {
            A = A * (k - x[j] + mod) % mod;
            B = B * (x[i] - x[j] + mod) % mod;
        }
        resi = resi * A % mod * ksm(B) % mod;
        res += resi;
    }
    return res % mod;
}


template<class T> 
T exgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    T g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
template<class T>
T getInv(T a, T p) {
    T x, y;
    exgcd(a, p, x, y);
    return (x % p + p) % p;
}
template<class T>
T chinese(vector<T> a, vector<T> p) {
    T P = 1;
    for (auto x : p) P *= x;
    T res = 0;
    for (int i = 0; i < a.size(); i++) {
        T M = P / p[i];
        T resi = (lll)a[i] * (M) % P * getInv(M, p[i]) % P;
        res += resi;
        if (res > P) res -= P;
    }
    return res % P;
}


// FWT
const int mod = 998244353;
ll ksm(ll a, ll b = mod - 2) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod, b /= 2;
    }
    return res;
} 
void Orr(vector<int> &a, int tp = 1) {
    int n = a.size(), m = __lg(n);
    for (int i = 0; i < m; i++) {
        int len = 1 << i;
        for (int j = 0; j < n; j += len * 2) {
            for (int k = 0; k < len; k++) {
                ll v = a[j + k + len] + a[j + k] * tp;
                if (tp == 1 && v >= mod) v -= mod;
                else if (v < 0) v += mod;
                a[j + k + len] = v;
            }
        }
    }
}
vector<int> Or(vector<int> a, vector<int> b) {
    Orr(a), Orr(b);
    for (int i = 0; i < a.size(); i++) a[i] = a[i] * 1ll *  b[i] % mod;
    Orr(a, -1);
    return a;
}


void Andd(vector<int> &a, int tp = 1) {
    int n = a.size(), m = __lg(n);
    for (int i = 0; i < m; i++) {
        int len = 1 << i;
        for (int j = 0; j < n; j += len * 2) {
            for (int k = 0; k < len; k++) {
                ll v = a[j + k + len] * tp + a[j + k];
                if (tp == 1 && v >= mod) v -= mod;
                else if (v < 0) v += mod;
                a[j + k] = v;
            }
        }
    }
}
vector<int> And(vector<int> a, vector<int> b) {
    Andd(a), Andd(b);
    for (int i = 0; i < a.size(); i++) a[i] = a[i] * 1ll *  b[i] % mod;
    Andd(a, -1);
    return a;
}


void Xorr(vector<int> &a, int tp = 1) {
    int n = a.size(), m = __lg(n);
    for (int i = 0; i < m; i++) {
        int len = 1 << i;
        for (int j = 0; j < n; j += len * 2) {
            for (int k = 0; k < len; k++) {
                ll v0 = a[j + k + len] + a[j + k];
                ll v1 = -a[j + k + len] + a[j + k];
                if (v0 >= mod) v0 -= mod; if (v1 < 0) v1 += mod;
                v0 *= tp, v1 *= tp;
                a[j + k] = v0 % mod, a[j + k + len] = v1 % mod;
            }
        }
    }
}
vector<int> Xor(vector<int> a, vector<int> b) {
    Xorr(a), Xorr(b);
    for (int i = 0; i < a.size(); i++) a[i] = a[i] * 1ll *  b[i] % mod;
    Xorr(a, ksm(2));
    return a;
}



/*
高斯消元异或线性基
性质：1. 每个答案的最高位1只有一个
*/
template<class T>
vector<T> xorbase(vector<T> a) {
    if (a.size() == 0) return {};
    
    int n = a.size(), k = 0;
    T mx = *max_element(a.begin(), a.end());
    if (mx <= 0) return {};

    for (int j = __lg(mx); j >= 0; j--) {
        for (int i = k; i < n; i++) {
            if (a[i] >> j & 1) { swap(a[i], a[k]); break; }
        }
        if ((a[k] >> j & 1) == 0) continue;
        for (int i = 0; i < n; i++) {
            if (i == k) continue;
            if (a[i] >> j & 1) a[i] ^= a[k];
        }
        k++; if (k >= n) break;
    }
    return vector<T>(a.begin(), a.begin() + k);
}


/*
min25筛第一部分，求质数的多项式和。
 */
vector<int> visi, pri; int cpri;
void init(int N) {
    N++;
    visi.assign(N, 0), pri.assign(N, 0);
    for (int i = 2; i < N; i++) {
        if (!visi[i]) {
            visi[i] = i;
            pri[++cpri] = i;
        }
        for (int j = 1; j <= cpri; j++) {
            int id = pri[j] * i;
            if (id >= N) break;
            visi[id] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
struct min25 {
    // 幂次k=1
    ll sn, n;
    vector<int> id;
    vector<ll> g;
    int getid(ll x) {
        if (x <= sn) return x;
        return id[n / x];
    }
    min25(ll N) {
        n = N;
        sn = sqrt((long double)n);
        init(2 * sn + 10); // todo

        id.assign(sn + 1, 0);
        g.assign(sn * 2 + 1, 0);
        vector<ll> big(sn * 2 + 1), G(sn + 1);
        
        for (int i = 2; i <= sn; i++) {
            G[i] = G[i - 1] + (visi[i] == i);
        }
        for (int i = 1; i <= sn; i++) {
            id[i] = 2 * sn + 1 - i;
            big[i] = i, big[id[i]] = n / i;
        }

        for (int i = 1; i <= sn * 2; i++) {
            g[i] = big[i] - 1; // todo 除了1所有数的k次方前缀和
        }

        for (int j = 1, beg = 1; pri[j] <= sn; j++) {
            while (j > 1 && beg <= sn * 2 && pri[j] * 1ll * pri[j] > big[beg]) beg++;
            for (int i = sn * 2; i >= beg; i--) {
                ll k = 1; // todo pri[j] ^ k
                g[i] = g[i] - k * (g[getid(big[i] / pri[j])] - G[pri[j - 1]]);
            }
        }
    }
    ll get(ll n) {
        return g[getid(n)];
    }
};
